import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Hashtable;

/**
 * 
 * We assume the input is the dependency graph, where each
 * dependency is between two classes in corresponding JAR 
 * packages.
 * Every class can be in source form (.java) or in binary form 
 * (.class). A source form class is called a definition, whereas
 * a binary form class is called a declaration.
 * 
 * The format of the dependency graph is a file where every line
 * expresses a dependency. A line is splitted by ",", the first
 * field after the split is the depender class whereas the rest of
 * fields are the dependees.
 * A class is separated by ":", to the left of the separator is
 * the JAR container's name, to the right of the separator is the
 * class file name.
 * When the class file name is ended with ".class", it is considered
 * a declaration, while other suffixes such as ".java" is considered
 * a definition.
 *  
 * @author yy66
 *
 */
public class Dependency {

	HashSet<String> u = new HashSet<String>(); // units
	HashSet<String> h = new HashSet<String>(); // declarations
	HashSet<String> c = new HashSet<String>(); // definitions

	HashSet<String> d = new HashSet<String>(); // dependencies

	HashSet<String> H = new HashSet<String>(); // header units
	HashSet<String> C = new HashSet<String>(); // compilation units
		
	// partitioning: class => package 
	Hashtable<String, String> P = new Hashtable<String, String>(); 

	// condensed dependencies between classes and C
	HashSet<String> D1 = new HashSet<String>(); 
	
	// transitive closure
	Hashtable<String, HashSet<String>> T = new Hashtable<String, HashSet<String>>(); 
	
	// package dependencies: package => package
	HashSet<String> D = new HashSet<String>(); // dependencies
	
	public static void main(String args[]) {
		Dependency g = new Dependency();
		g.input_dependency_graph(args[0]);
		g.condensing();
		g.transitive_closure();
		g.partitioning();		
		g.output_dependency_graph();
	}

	void output_dependency_graph() {
		System.out.println("--\nDeclarations are:");
		for (String n: h) {
			System.out.println(n);
		}
		System.out.println("--\nDefinitions are:");
		for (String n: c) {
			System.out.println(n);
		}
		System.out.println("--\nLibrary packages are:");
		for (String n: H) {
			System.out.println(n);
		}
		System.out.println("--\nCompilation packages are:");
		for (String n: C) {
			System.out.println(n);
		}
		System.out.println("--\nDependencies are:");
		for (String n: d) {
			System.out.println(n);
		}		
		System.out.println("--\nCondensed dependencies are:");
		for (String n: D1) {
			System.out.println(n);
		}		
		System.out.println("--\nTransitive closures are:");
		for (String n: T.keySet()) {
			System.out.println(n + ":" + T.get(n));
		}		
		System.out.println("--\nPartitions are:");
		for (String n: P.keySet()) {
			System.out.println(n + ":" + P.get(n));
		}		
		System.out.println("--\nDependencies between restructured packages are:");
		for (String n: D) {
			System.out.println(n);
		}		
	}

	void input_dependency_graph(String filename) {
		try {
		BufferedReader br = new BufferedReader(new 
				FileReader( new File(filename)));
		String line = null;
		while((line = br.readLine())!=null) {
			String fields[] = line.split(",");
			if (fields.length > 0) {
				add_symbol(fields[0]);
			}
			for (int i=1; i<fields.length; i++) {
				add_symbol(fields[i]);
				d.add(fields[0] + "," + fields[i]);
			}
		}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	private void add_symbol(String name) {
		String pkg = null;
		if (name.contains(":")) {
			String ns[] = name.split(":");
			if (ns[0].endsWith(".jar")) {
				pkg = ns[0];
			}
			name = ns[1];
		}
		u.add(name);
		if (isDeclaration(name)) {
			h.add(name);
			if (pkg!=null)
				H.add(pkg);
		} else {
			c.add(name);
			if (pkg!=null)
				C.add(pkg);
		}
	}

	boolean isDeclaration(String name) {
		if (name.endsWith(".class")) {
			return true;
	 	}
		return false;
	}

	/**
	 * In this step, the dependency graph is simplified to
	 * between dependee's JAR package and the dependers.
	 * 
	 * Because we assume the source code are not shuffled,
	 * only the required libraries are. 
	 */
	void condensing() {
		for (String n: d) {
			String fields[] = n.split(",");
			String pkg = getPackage(fields[0]);
			String s = fields[0];
			if (pkg!=null) 
				s = pkg;
			for (int i=1; i< fields.length; i++) {
				s += "," + fields[i];
			}
			D1.add(s);
		}
	}
	
	/**
	 * The transitive closure is defined as the source packages
	 * that the declaration classes are depended on.
	 * 
	 * @FIXME: might be more efficient if computed in the topological order
	 */
	void transitive_closure() {
		boolean changed = false;
		do {
			changed = false;
		for (String n: D1) {
			String fields[] = n.split(",");
			HashSet<String> pkgs = new HashSet<String> ();
			if (!fields[0].endsWith(".jar")) {
				if(T.get(fields[0])!=null) {
					pkgs.addAll(T.get(fields[0]));
				}
			} else {
				String pkg = fields[0];
				pkgs.add(pkg);
			}
			for (int i=1; i< fields.length; i++) {
				HashSet<String> closure = T.get(fields[i]);
				if (closure==null) {
					closure = new HashSet<String>();
				}
				if (!closure.containsAll(pkgs)) {
					closure.addAll(pkgs);	
					changed = true;
				}
				T.put(fields[i], closure);
			}
		}		
		} while (changed);
	}
	
	/**
	 * return the name of the JAR package if any
	 * @param name
	 * @return
	 */
	private String getPackage(String name) {
		String pkg = null;
		if (name.contains(":")) {
			String ns[] = name.split(":");
			if (ns[0].endsWith(".jar")) {
				pkg = ns[0];
			}
		}
		return pkg;
	}

	/**
	 * merge the classes that have the same transitive closure
	 */
	void partitioning() {
		HashSet<HashSet<String>> sets = new HashSet<HashSet<String>>();
		for (String t: T.keySet()) {
			HashSet<String> set = T.get(t);
			sets.add(set);
		}
		Hashtable<HashSet<String>, String> table = new Hashtable<HashSet<String>, String>(); 
		int partition = 0;
		for (HashSet<String> set: sets) {
			table.put(set, "" + partition);
			partition++;
		}		
		dependency_by_partial_ordering_of_set_inclusion(sets, table);
		for (String t: T.keySet()) {
			P.put(t, table.get(T.get(t)));
		}
	}

	private void dependency_by_partial_ordering_of_set_inclusion(
			HashSet<HashSet<String>> sets,
			Hashtable<HashSet<String>, String> table) {
		for (HashSet<String> set1: sets) {
			for (HashSet<String> set2: sets) {
				if (set1!=set2) {
					if (set1.containsAll(set2))
						D.add(table.get(set2) + "," + table.get(set1));
				}
			}
		}
	}	
}
